package demo.practice.bit;

import java.util.HashMap;
import java.util.Map;

class Trie {

    public boolean isWord;
    //public  int size;
    Map<Character, Trie> child = new HashMap<>();

    public Trie() {
        this.isWord = false;
    }

    public void insert(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.child.get(c) == null) {
                cur.child.put(c, new Trie());
                cur = cur.child.get(c);   //迭代到下一个节点
            } else {
                cur = cur.child.get(c);   //迭代到下一个节点
            }
        }
        cur.isWord = true;//表示当前字符是一个单词的结尾
    }


    public boolean search(String word) {
        Trie cur = this;
        for (char c : word.toCharArray()) {
            if (cur.child.get(c) == null) {
                return false;
            } else {
                cur = cur.child.get(c);
            }
        }
        return cur.isWord;//返回当前这个节点是不是一个单词的结尾
    }

    public boolean startsWith(String prefix) {
        Trie cur = this;
        for (char c : prefix.toCharArray()) {
            if (cur.child.get(c) == null) {
                return false;
            } else {
                cur = cur.child.get(c);
            }
        }
        return true;//返回当前这个节点是不是一个单词的结尾
    }
}


class PP421Trie {
    Map<Integer, PP421Trie> child = new HashMap<>();
    //public boolean isEnd;

    public void insert(int num) {
        PP421Trie cur = this;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (cur.child.get(bit) == null) {
                cur.child.put(bit, new PP421Trie());
                cur = cur.child.get(bit);
            } else {
                cur = cur.child.get(bit);
            }
        }


        //cur.isEnd=true;
    }

    public void insert(int[] nums) {
        for (int num : nums) {
            insert(num);
        }
    }


    public int XorMax(int num) {
        PP421Trie cur = this;
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                if (cur.child.get(1) != null) {
                    //这一位有值
                    res = res | (1 << i);
                    cur = cur.child.get(1);
                } else {
                    cur = cur.child.get(0);
                }
            } else {
                if (cur.child.get(0) != null) {
                    //这一位有值
                    res = res | (1 << i);
                    cur = cur.child.get(0);
                } else {
                    cur = cur.child.get(1);
                }
            }
        }
        return res;
    }

    public int XorMax(int[] nums) {
        int max = 0;
        for (int num : nums) {
            System.out.println(XorMax(num));
            max = Math.max(XorMax(num), max);
        }
        return max;
    }
}


public class P421_2 {
    public static void main(String[] args) {
        P421_2 p421_2 = new P421_2();
        int maximumXOR = p421_2.findMaximumXOR(new int[]{3, 10, 5, 25, 2, 8});
        System.out.println(maximumXOR);


    }

    public int findMaximumXOR(int[] nums) {
        PP421Trie t = new PP421Trie();
        t.insert(nums);
        return t.XorMax(nums);
    }


}
